We established that efficient sorting is crucial for subsequent operations, transforming unstructured data $A$ into structured data $B$ to enable fast searches and complex data structure construction. Now, let's formally define the two criteria that any algorithm must meet to be considered a correct sort, ensuring the transformation from input array $A$ to output array $B$ is mathematically valid.
- The core task is to take an input list $A$ of size $n$, and produce a new list $B$ that satisfies two non-negotiable requirements, both of which must hold true for all $n$ elements:
- Requirement 1: Preservation (Permutation): The output list $B$ must be a permutation of the input list $A$. This is fundamental: the algorithm cannot change the elements themselves, only their positions. If $A$ contains three copies of the value 5, $B$ must also contain exactly three copies of 5.
- Requirement 2: Order: The elements in $B$ must be arranged according to the designated criterion (typically non-decreasing, or ascending, order). If this property is not met, the resulting list cannot be used efficiently by algorithms like Binary Search.
Sorting Correctness
An algorithm correctly sorts the input array $A$ (size $n$) into array $B$ if and only if the following properties are satisfied simultaneously.
$$ \text{Input: } A = [a_1, \ldots, a_n] \qquad \text{Output: } B = [b_1, \ldots, b_n] $$
$$ \text{I. Permutation Constraint: } B \text{ is a valid permutation of } A $$
$$ \text{II. Order Constraint (Ascending): } b_i \le b_{i+1} \quad \text{for } 1 \le i < n $$